// https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

// 题干：给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
//      注意 这个数列必须是 严格 递增的。

// 示例：输入: [1,3,5,4,7]
//      输出: 2

// 碎语：在数组中找出最大值出现的次数，要求一次遍历解决问题
//       办法是贪心策略，申请两个变量maxVal count分三种情况讨论

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int findNumberOfLIS(vector<int>& nums)
    {
        // 以某个位置为结尾，计算长度，然后用两个变量再来遍历一遍数组
        int n = nums.size(); if (n == 1) return 1;
        vector<int> len(n, 1), count(n, 1);

        for (int i = 1 ; i < n ; i++){
            for (int j = 0 ; j < i ; j++){
                if (nums[j] < nums[i]){
                    if (len[j] + 1 == len[i]) count[i] += count[j];
                    else if (len[j] + 1 > len[i]) {len[i] = len[j] + 1; count[i] = count[j];}
                }
            }
        }

        int retLen = 1, retCount = 1;
        for (int i = 1 ; i < n ; i++){
            if (retLen == len[i]) retCount += count[i];
            else if (retLen < len[i]) retLen = len[i], retCount = count[i];
        }

        return retCount;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,3,5,4,7};

    cout << sol.findNumberOfLIS(nums) << endl;

    return 0;
}

